﻿#ifndef GraphAlgorithms_h__
#define GraphAlgorithms_h__

/********************************************************************
	创建于:		2011/03/22
	创建于:		22:3:2011   15:53
	基本文件:	GraphAlgorithms
	文件扩展:	h
	作者:		王凯
	
	目的:		提供DFS、BFS、A*和Dijkstra搜索算法的支持。
				必须使用和SparseGraph类相同接口的图才能正常运行。
*********************************************************************/

#include <vector>
#include <list>
#include <stack>//dfs
#include <queue>//bfs
#include "SparseGraph.h"
#include "DateStructures/PriorityQueue.h"//from mat
#include "AStarHeuristicPolicies.h"

//DFS搜索算法类
template<typename graph_type>
class Graph_SearchDFS
{
private:
	typedef typename graph_type::NodeType Node;
	typedef typename graph_type::EdgeType Edge;

	//标记节点是否被访问过和没有父节点
	enum{ visited, unvisited, no_parent_assigned};

	//需要搜索的图
	const graph_type& m_Graph;

	//辅助数组，用来标记节点是否被访问
	std::vector<int> m_Visited;

	//辅助数组，用来标记节点的上一个节点
	//索引为2的节点结果为1表示2的节点父节点为1
	std::vector<int> m_Route;

	//生成树
	std::vector<const Edge*> m_SpanningTree;

	//标记搜索是否完成
	bool m_bFound;

	//存放目标节点和起始节点的索引
	int m_iSource;
	int m_iTarget;

	//内部调用Search来搜索路径
	bool Search();

public:

	Graph_SearchDFS(const graph_type& g, int s,int t = -1):
	  m_Graph(g), m_iSource(s), m_iTarget(t), m_bFound(false), 
		  m_Route(m_Graph.NumNodes(), no_parent_assigned),
		  m_Visited(m_Graph.NumNodes(), unvisited)
	  {
		  m_bFound = Search();
	  }

	  //返回最短路径树
	  std::vector<const Edge*> GetSearchTree() const{ return m_SpanningTree;}

	  //如果搜索完成则返回真，否则返回假
	  bool Found()const{ return m_bFound;}

	  //返回一个从起点到目标点的链表
	  std::list<int> GetPathToTarget()const;

};

template<class graph_type>
bool Graph_SearchDFS<graph_type>::Search()
{
	//创建一个栈作为DFS搜索的关键
	std::stack<const Edge*> stack;
	//创建一个哑边
	Edge dummy(m_iSource, m_iSource, 0);
	//将哑边压栈
	stack.push(&dummy);
	//开始DFS
	while(!stack.empty())
	{
		//将栈顶的元素弹栈
		const Edge* nextEdge = stack.top();
		stack.pop();
		//让From成为To的父节点
		m_Route[nextEdge->To()] = nextEdge->From();
		//判断改变是否是哑边
		if(nextEdge != &dummy)
		{
			//不是，则放入最短路径树的尾部
			m_SpanningTree.push_back(nextEdge);
		}
		//标志该边已经访问
		m_Visited[nextEdge->To()] = visited;

		//是否已经找到
		if(nextEdge->To() == m_iTarget)
		{
			//找到，返回真
			return true;
		}
		//用来遍历nextEdge->To的所有邻接点
		graph_type::ConstEdgeIterator ConstEdgeItr(m_Graph, nextEdge->To());
		//依次遍历
		for(const Edge* pE = ConstEdgeItr.begin(); !ConstEdgeItr.end(); pE = ConstEdgeItr.next())
		{
			//如果该点未被访问，则压入栈中
			if(m_Visited[pE->To()] == unvisited)
				stack.push(pE);
		}
	}
	//没有找到
	return false;
}

template<class graph_type>
std::list<int> Graph_SearchDFS<graph_type>::GetPathToTarget()const
{
	std::list<int> path;
	//没有找到或者目标没有指定时，直接返回
	//一个空链表
	if(!m_bFound || m_iTarget == -1)
		return path;
	//先将目标的索引保存
	int nd = m_iTarget;
	path.push_back(nd);

	//不断向上查找nd的父节点
	//知道nd是起点为止
	while(nd != m_iSource)
	{
		nd = m_Route[nd];
		path.push_back(nd);
	}

	//返回路径
	return path;
}


//BFS搜索算法类
template<typename graph_type>
class Graph_SearchBFS
{
private:
	typedef typename graph_type::NodeType Node;
	typedef typename graph_type::EdgeType Edge;

	//标记节点是否被访问过和没有父节点
	enum{ visited, unvisited, no_parent_assigned};

	//需要搜索的图
	const graph_type& m_Graph;

	//辅助数组，用来标记节点是否被访问
	std::vector<int> m_Visited;

	//辅助数组，用来标记节点的上一个节点
	//索引为2的节点结果为1表示2的节点父节点为1
	std::vector<int> m_Route;

	//生成树
	std::vector<const Edge*> m_SpanningTree;

	//标记搜索是否完成
	bool m_bFound;

	//存放目标节点和起始节点的索引
	int m_iSource;
	int m_iTarget;

	//内部调用Search来搜索路径
	bool Search();

public:
	Graph_SearchBFS(const graph_type& g,int s, int t = -1)
		:m_Graph(g),m_iSource(s),m_iTarget(t),m_bFound(false),
		m_Route(g.NumNodes(), no_parent_assigned),
		m_Visited(g.NumNodes(), unvisited)
	{
		m_bFound = Search();
	}

	//返回最短路径树
	std::vector<const Edge*> GetSearchTree() const{ return m_SpanningTree;}

	//如果搜索完成则返回真，否则返回假
	bool Found()const{ return m_bFound;}

	//返回一个从起点到目标点的链表
	std::list<int> GetPathToTarget()const;
};

template<typename graph_type>
bool Graph_SearchBFS<graph_type>::Search()
{
	//创建队列存放边
	std::queue<const Edge*> Q;
	//创建一个哑边
	const Edge Dummy(m_iSource, m_iSource, 0);
	//让哑边入队
	Q.push(&Dummy);
	//将起点标识为已访问
	m_Visited[m_iSource] = visited;

	//开始BFS
	while(!Q.empty())
	{
		//取出一个队列中元素
		const Edge* next = Q.front();
		Q.pop();

		//让From成为To的父节点
		m_Route[next->To()] = next->From();

		//判断当前节点是否是哑边，不是则放入最短路径树中
		if(next != &Dummy)
			m_SpanningTree.push_back(next);

		//找到
		if(next->To() == m_iTarget)
			return true;

		//循环访问To顶点所在的每一个边
		graph_type::ConstEdgeIterator ConstEdgeItr(m_Graph, next->To());
		for(const Edge* pE= ConstEdgeItr.begin();
			!ConstEdgeItr.end();
			pE = ConstEdgeItr.next())
		{
			//只要To的TO顶点没有访问，则入队列并标记为访问
			if(m_Visited[pE->To()] == unvisited)
			{
				Q.push(pE);
				m_Visited[pE->To()] = visited;
			}
		}	
	}
	//没找到
	return false;
}

template<typename graph_type>
std::list<int> Graph_SearchBFS<graph_type>::GetPathToTarget()const
{
	std::list<int> path;
	//没有找到或者目标没有指定时，直接返回
	//一个空链表
	if(!m_bFound || m_iTarget == -1)
		return path;
	//先将目标的索引保存
	int nd = m_iTarget;
	path.push_back(nd);

	//不断向上查找nd的父节点
	//知道nd是起点为止
	while(nd != m_iSource)
	{
		nd = m_Route[nd];
		path.push_back(nd);
	}

	//返回路径
	return path;
}

//Dijkstra搜索算法类
template<typename graph_type>
class Graph_SearchDijkstra
{
private:
	typedef typename graph_type::EdgeType Edge;

	const graph_type& m_Graph;
	std::vector<const Edge*> m_ShortesPathTree;
	std::vector<const Edge*> m_SearchFrontier;
	std::vector<double> m_CostToThisNode;

	int m_iSource;
	int m_iTarget;
public:
	Graph_SearchDijkstra(const graph_type& g, int s, int t = -1):
	  m_Graph(g), m_iSource(s), m_iTarget(t),
		  m_SearchFrontier(g.NumNodes()),
		  m_ShortesPathTree(g.NumNodes()),
		  m_CostToThisNode(g.NumNodes())
	  {
		  Search();
	  }

	void Search();
	std::vector<const Edge*> GetSPT()const { return m_ShortesPathTree;}
	std::list<int> GetPathToTarget() const;
	double GetCostToTarget()const{ return m_CostToThisNode[m_iTarget];}
	double GetCostToNode(unsigned int nd)const{ return m_CostToThisNode[nd];}
};

template<typename graph_type>
std::list<int> Graph_SearchDijkstra<graph_type>::GetPathToTarget() const
{
	std::list<int> path;
	if(m_iTarget < 0)
		return path;

	int nd = m_iTarget;
	path.push_back(nd);
	
	while((nd != m_iSource) && (m_ShortesPathTree[nd] != 0))
	{
		nd = m_ShortesPathTree[nd]->From();
		path.push_front(nd);
	}

	return path;
}

template<typename graph_type>
void Graph_SearchDijkstra<graph_type>::Search()
{
	//优先队列
	IndexedPriorityQLow<double> pq(m_CostToThisNode, m_Graph.NumNodes());
	//下一个最近顶点的索引
	int NextClosestNode;
	//存放新的路径权值
	int NewCost;
	//将起点入队
	pq.insert(m_iSource);

	while(!pq.empty())
	{
		//弹出队列中权值最小点最为最近顶点（索引）
		NextClosestNode = pq.Pop();

		//把这条边从搜索边界移动到最短路径树上
		m_ShortesPathTree[NextClosestNode] = m_SearchFrontier[NextClosestNode];
		//找到跳出
		if(NextClosestNode == m_iTarget)
			return;

		//遍历每一条连接下一个最近顶点的边
		graph_type::ConstEdgeIterator ConstEdgeItr(m_Graph, NextClosestNode);
		for(const Edge* pE = ConstEdgeItr.begin();
			!ConstEdgeItr.end();
			pE = ConstEdgeItr.next())
		{
			//计算新的权值 = 该点到目标顶点的权 + 起点到该点的权
			NewCost = m_CostToThisNode[NextClosestNode] + pE->Cost();
			if(m_SearchFrontier[pE->To()] == 0)
			{
				//赋值新权值
				m_CostToThisNode[pE->To()] = NewCost;
				//将该边目标顶点加入队列
				pq.insert(pE->To());
				m_SearchFrontier[pE->To()] = pE;
			}
			else if(NewCost < m_CostToThisNode[pE->To()]&&
				m_ShortesPathTree[pE->To() == 0])
			{
				m_CostToThisNode[pE->To()] = NewCost;
				pq.ChangePriority(pE->To());
				m_SearchFrontier[pE->To()] = pE;
			}
				
		}
	}
}

//A*搜索算法类
template<typename graph_type, typename heuristic>
class Graph_SearchAStar
{
private:
	typedef typename graph_type::EdgeType Edge;

	const graph_type& m_Graph;

	std::vector<const Edge*> m_ShortestPathTree;
	std::vector<const Edge*> m_SearchFrontier;
	std::vector<double> m_GCost;
	std::vector<double> m_FCost;

	int m_iSource;
	int m_iTarget;

	void Search();

public:
	Graph_SearchAStar(graph_type &graph, int source, int target = -1):
	  m_Graph(graph), m_iSource(source), m_iTarget(target),
		  m_ShortestPathTree(graph.NumNodes()),
		  m_SearchFrontier(graph.NumNodes()),
		  m_GCost(graph.NumNodes(), 0.0),
		  m_FCost(graph.NumNodes(), 0.0)
	  {
		  Search();
	  }

	  std::vector<const Edge*> GetSPT()const{return m_ShortestPathTree;}

	  std::list<int> GetPathToTarget()const;

	  double GetCostToTarget()const{return m_GCosts[m_iTarget];}
};

template<typename graph_type, typename heuristic>
void Graph_SearchAStar<graph_type, heuristic>::Search()
{
	IndexedPriorityQLow<double> pq(m_FCost, m_Graph.NumNodes());
	int NextClosestNode;
	double HCost;
	double GCost;

	pq.insert(m_iSource);

	while(!pq.empty())
	{
		NextClosestNode = pq.Pop();

		m_ShortestPathTree[NextClosestNode] = m_SearchFrontier[NextClosestNode];
		if(NextClosestNode == m_iTarget)
			return;

		graph_type::ConstEdgeIterator ConstEdgeItr(m_Graph, NextClosestNode);
		for(const Edge* pE = ConstEdgeItr.begin();
			!ConstEdgeItr.end();
			pE = ConstEdgeItr.next())
		{
			HCost = heuristic::Calculate(m_Graph, NextClosestNode, pE->To());

			GCost = m_GCost[NextClosestNode] + pE->Cost();

			if(m_SearchFrontier[pE->To()] == 0)
			{
				m_FCost[pE->To()] = HCost + GCost;
				m_GCost[pE->To()] = GCost;
				pq.insert(pE->To());

				m_SearchFrontier[pE->To()] = pE;
			}

			else if(GCost < m_GCost[pE->To()] &&
				m_ShortestPathTree[pE->To()] == 0)
			{
				m_FCost[pE->To()] = HCost + GCost;
				m_GCost[pE->To()] = GCost;
				pq.ChangePriority(pE->To());

				m_SearchFrontier[pE->To()] = pE;
			}
		}
	}
}

template<typename graph_type, typename heuristic>
std::list<int> Graph_SearchAStar<graph_type, heuristic>::GetPathToTarget() const
{
	std::list<int> path;
	if(m_iTarget < 0)
		return path;

	int nd = m_iTarget;
	path.push_back(nd);

	while((nd != m_iSource) && (m_ShortestPathTree[nd] != 0))
	{
		nd = m_ShortestPathTree[nd]->From();
		path.push_back(nd);
	}
	
	return path;
}

#endif // GraphAlgorithms_h__